package 算法;

public class 数组类算法 {
    public static void main(String[] args) {
        int[] a = new int[]{1,2,3,0,0,0};
        int[] b = new int[]{4,5,6};

        new 数组类算法().merge(a,3,b,3);
        System.out.println(new 数组类算法().two(new int[]{1,2,3,4,5},6,0,4));
    }
    //采用对撞指针
    public int[] twoSum1(int[] numbers, int target){
        int i = 0,j = numbers.length-1;
        int[] res = new int[2];
        while (true){
            if(numbers[i] + numbers[j] == target){
                res[0] = i+1;
                res[1] = j+1;
                return res;
            }else if(numbers[i] + numbers[j] > target){
                j--;
            }else {
                i++;
            }
        }
    }

    public int[] twoSum(int[] numbers, int target) {
        int[] j = new int[2];
        int len = numbers.length;
        for (int i = 0; i < len; i++) {
            if(numbers[i] > target) break;
            int k = two(numbers,target - numbers[i],i,len-1);
            if(k != -1){
                j[0] = i;
                j[1] = k;
            }
        }
        return j;
    }
    //二分查找   ，找到返回下标，否则返回-1      [left,right]
    public int two(int[] numb,int target,int left,int right){

        int middle = left + (right-left)/2;
        if(middle==left) {
            if(numb[left] == target) return left;
            else if(numb[right] == target) return right;
            return -1;
        }

        if(numb[middle] == target) return middle;
        else if(numb[middle] > target) return two(numb,target,left,middle);
        else return two(numb,target,middle,right);
    }
    public void moveZeroes(int[] nums) {
        int j = 0; //j是慢指针，i是快指针
        for (int i = 0; i < nums.length; i++) {
            if(nums[i] != 0){
                nums[j] = nums[i];
                j++;
            }
        }
        for (int i = j; i < nums.length; i++) {
            nums[i] = 0;
        }

    }
    public int removeDuplicates(int[] nums) {
        int j = 0; //j是慢指针，i是快指针
        for (int i = 1; i < nums.length; i++) {
            if(nums[i] != nums[j]){
                nums[++j] = nums[i];
            }
        }
        return j+1;
    }
    public int removeDuplicates2(int[] nums) {
        int fla = 0;//0代表没重复，1代表重复1次，2代表重复大于1次
        int j = 0; //j是慢指针，i是快指针
        for (int i = 1; i < nums.length; i++) {
            if(nums[i] == nums[j]){
                if(fla == 0){
                    fla++;
                    j++;
                    nums[j] = nums[i];
                }else if(fla == 1){
                    fla++;
                }
            }else {
                fla = 0;
                nums[++j] = nums[i];
            }
        }
        return j+1;
    }
    public void sortColors(int[] nums) {

        int l = -1;
        int r = nums.length;
        for (int i = 0; i < r && l < r;i++ ) {
            if(nums[i] == 0){
                l++;
                swap(nums,i,l);
            }else if(nums[i] == 2){
                r--;
                swap(nums,r,i);
                i--;
            }
        }
    }
    public int findKthLargest(int[] nums, int k) {
//        int lastNode = nums.length/2 - 1; //返回最后一个叶子节点
        for (int i = 0; i < k; i++) {

            zuiPai(nums,nums.length-i);
            if(i+1 >= k) return nums[0];
            int temp  = nums[nums.length-i-1];
            nums[nums.length-i-1] = nums[0];
            nums[0] = temp;
        }
        return nums[0];

    }
    public void zuiPai(int[] nums,int life){
        for (int lastNode = nums.length/2 - 1;lastNode >= 0; lastNode--){
            int left = lastNode*2+1,right= lastNode*2+2;
            if(left < life) max(nums,lastNode,left);
            if(right < life) max(nums,lastNode,right);
        }
    }
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m+n-1;
        m--;n--;
        while (true){
            if(m < 0 || n < 0) break;
            nums1[i--] = nums1[m] >= nums2[n] ? nums1[m--]:nums2[n--];
        }
        if(m >= 0){
            while (m>=0){
                nums1[i--] = nums1[m--];
            }
        }else
            while (n>=0){
                nums1[i--] = nums2[n--];
            }
    }
    //i对应的元素值为最大值
    public void max(int[] nums,int i,int j){
        if(nums[j] > nums[i]){
           int t = nums[j];
           nums[j] = nums[i];
           nums[i] = t;
        }
    }
    public void swap(int[] nums,int frist,int last){
        int temp = nums[frist];
        nums[frist] = nums[last];
        nums[last] = temp;
    }
}
